﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Atlepage.Syntactic
{
    public class ParserFactory
    {
        Dictionary<string, NonTerminal> nonTerms = new Dictionary<string, NonTerminal>();
        Dictionary<string, Terminal> terms = new Dictionary<string, Terminal>();
        List<Production> productions = new List<Production>();
        List<LRItemSet> states = new List<LRItemSet>();
        Parser parser;

        public ParserFactory()
        {
        }

        public Parser CreateParser(object actor)
        {
            Parser parser = this.parser.Clone();
            parser.Initialize(actor);
            return parser;
        }

        public bool Generate(Type type, IEnum kind, List<string> errors, List<string> warnings)
        {
            errors.Clear();
            warnings.Clear();

            StartAttribute[] starts = (StartAttribute[])type.GetCustomAttributes(typeof(StartAttribute), true);
            if (starts.Length != 1)
            {
                errors.Add("There must be exactly one StartAttribute on the parser type");
                return false;
            }

            productions.AddRange(
                from m in type.GetMethods()
                from a in (RuleAttribute[])m.GetCustomAttributes(typeof(RuleAttribute), true)
                where m.Name.StartsWith("p_") || a.Name != null
                from p in Production.Parse(m, a.Name == null ? m.Name.Substring(2) : a.Name, a.Rule, kind, nonTerms, terms)
                select p);

            NonTerminal oldStart;
            if (!nonTerms.TryGetValue(starts[0].NonTerminal, out oldStart))
            {
                errors.Add("The selected start symbol was not found.");
                return false;
            }

            foreach (var item in from x in nonTerms where !x.Value.HasProductions select x.Value)
            {
                errors.Add("The non terminal '" + item + "' has no productions");
            }
            if (errors.Count > 0)
                return false;

            NonTerminal ntStart = new NonTerminal("$TART");
            Production pStart = new Production(null, ntStart, new ProductionNode[] { oldStart });
            nonTerms.Add("$TART", ntStart);

            LRItem start = new LRItem(0, pStart);
            LRItem end = new LRItem(1, pStart);
            LRItemSet startSet = new LRItemSet();
            startSet.Add(start);

            List<LRItem> kernels = new List<LRItem>();
            Queue<LRItemSet> setQueue = new Queue<LRItemSet>();
            setQueue.Enqueue(startSet);
            while (setQueue.Count > 0)
            {
                LRItemSet set = setQueue.Dequeue();
                kernels.Add(set.Kernel);
                states.Add(set);

                Closure(set);

                GetChildSets(setQueue, set, kernels);
            }

            Parser.Action[,] actions = new Parser.Action[states.Count, kind.MaximumValue + 2];
            int[,] gotos = new int[states.Count, nonTerms.Count];
            List<NonTerminal> lNonTerms = new List<NonTerminal>(nonTerms.Values);
            List<Terminal> lTerms = new List<Terminal>(terms.Values);

            for (int i = 0; i < states.Count; i++)
                for (int j = 0; j < nonTerms.Count; j++)
                    gotos[i, j] = -1;

            for (int i = 0; i < states.Count; i++)
            {
                LRItemSet state = states[i];
                foreach (var item in state.Transitions)
                {
                    int newState = states.IndexOf(item.Value);
                    NonTerminal nt = item.Key as NonTerminal;
                    if (nt != null)
                    {
                        gotos[i, lNonTerms.IndexOf(nt)] = newState;
                        continue;
                    }
                    Terminal t = item.Key as Terminal;
                    if (t != null)
                    {
                        actions[i, t.Type] = new Parser.Shift(newState, item.Value);
                    }
                }
                foreach (var item in state)
                {
                    if (item.Dot != item.Production.Nodes.Length)
                        continue;

                    if (item.Equals(end))
                    {
                        actions[i, kind.MaximumValue + 1] = new Parser.Accept();
                        continue;
                    }

                    var reduce = new Parser.Reduce(lNonTerms, item.Production, productions.IndexOf(item.Production));
                    foreach (var t in GetTriggers(item, lTerms, kind))
                    {
                        actions[i,t] = ResolveConflict(reduce, actions[i,t], errors, warnings);
                    }
                }

            }

            parser = new Parser(actions, gotos);

            return errors.Count == 0;
        }

        private Parser.Action ResolveConflict(Parser.Reduce reduce, Parser.Action action, List<string> errors, List<string> warnings)
        {
            if (action == null)
                return reduce;
            if (action is Parser.Shift)
            {
                warnings.Add(action.Conflict(reduce));
                return action;
            }
            if (action.ToString() == reduce.ToString())
            {
                errors.Add(string.Format("Duplicate: {0} is declared twice", reduce.production));
                return reduce;
            }
            errors.Add(action.Conflict(reduce));
            return reduce;
        }

        private IEnumerable<int> GetTriggers(LRItem item, List<Terminal> lTerms, IEnum kind)
        {
            return Enumerable.Range(0, kind.MaximumValue + 2);
        }

        private void GetChildSets(Queue<LRItemSet> setQueue, LRItemSet parentSet, List<LRItem> kernels)
        {
            List<LRItem> list = new List<LRItem>();
            list.AddRange(from i in parentSet
                          where i.Dot < i.Production.Nodes.Length
                          select new LRItem(i.Dot + 1, i.Production));

            while (list.Count != 0)
            {
                LRItemSet childSet = new LRItemSet();
                LRItem child = list[0];

                childSet.AddRange(from i in list
                                  where i.Previous == child.Previous
                                  select i);
                foreach (var item in childSet)
                    list.Remove(item);

                if (!kernels.Contains(childSet.Kernel))
                    setQueue.Enqueue(childSet);
                else
                {
                    childSet = (from s in states 
                               where s.Kernel.Equals(childSet.Kernel)
                               select s).First();
                }
                parentSet.AddTransition(child.Previous, childSet);
            }
        }

        void Closure(LRItemSet set)
        {
            for (int ix = 0; ix < set.Count; ix++)
            {
                ProductionNode node = set[ix].Current;
                NonTerminal nt = node as NonTerminal;
                if (nt != null)
                {
                    set.AddRange(from p in nt.Productions
                                 select new LRItem(0, p));
                }
            }
        }
    }
}
